package uestc.lj.basic.tree;

/**
 * 判断一棵二叉树是否是满二叉树
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code08_IsFullTree {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static class Info {
		public int height;
		public int nodesCount;

		public Info(int height, int nodesCount) {
			this.height = height;
			this.nodesCount = nodesCount;
		}
	}

	public static boolean isFullTree(Node head) {
		if (head == null) {
			return true;
		}
		return process(head).nodesCount == (1 << process(head).height - 1);
	}

	public static Info process(Node head) {
		if (head == null) {
			return new Info(0, 0);
		}
		Info left = process(head.left);
		Info right = process(head.right);
		int heigth = Math.max(left.height, right.height) + 1;
		int nodesCount = left.nodesCount + right.nodesCount + 1;
		return new Info(heigth, nodesCount);
	}
}
